This application relates to multithreaded processing and, specifically, to multithreaded code processing.
Computer programs (hereafter xe2x80x9cprogramsxe2x80x9d) are written in order to handle a task, typically in response to some problem to be solved. Structurally, programs include program code in the form of statements written based on grammatical rules which are also referred to as the language syntax. Statements such as, for example, declaration, definition, assignment and function statements outline the type of, and the manner of creating and manipulating, data abstractions. A series of statements that manipulates one or more data abstractions can be viewed as a supporting abstraction and is referred to as an algorithm. Data abstractions represent any simple or complex data structure types that model abstract concepts or objects in the real world. Data structures may include a numerical value or any programmatic combination thereof, a dictionary entry, an array of objects, a decision flag, an entry in a database of electronic hardware components, or a basic electronic hardware item description. Generally, a program design identifies the candidate data obstructions of a task and/or problem domain, the supporting abstractions of an implementation of the task or solution, and the relationship between the various abstractions.
In a computer, the program design and execution is facilitated by an operating system. The operating system is charged with controlling the operations of a computer system. The operating system is responsible for managing computer system resources, as well as compiling programs to convert the statements in programs to an executable form and managing the execution of such programs once they are compiled and linked into executable modules. An operating system such as the UNIX operating system (hereafter xe2x80x9cUNIXxe2x80x9d) includes a kernel and system programs. UNIX is a registered trademark of UNIX Systems Laboratories, Inc. The kernel provides, by responding to system calls, a file system, a processor scheduling, memory management, etc. System programs include system libraries, compilers, interpreters, shells, etc. Compilers convert program statements (also known as source code) into object code. For example, a C compiler translates C source programs into object modules or into executable modules. An option of the C compiler (e.g., the -c option) causes the C compiler to produce an object module rather than an executable module.
In general, compilation of programs involves translation of program source code into object modules or executable modules that are ready to be loaded and executed. The compilation process, also referred to as language code processing, proceeds in stages. An initial input stage of a compiler performs a lexical analysis of symbols and tokens in the program statements. This phase is followed by parsing to determine the syntactic structure of statements in the program. In order to produce the syntactic structure of program statements, a parser normally takes as input a sequence of symbols and tokens output by a lexical analyzer. Since programs typically also includes statements for macro definitions and references to library and other header files to be included, a preprocessor expands the macros and includes the header files. Header files provide, for example, symbols definitions and function prototypes. The preprocessor copies header files into the source code programs prior to compilation. The macros represent the compiler options so that compiler options need only be changed in one place rather than in the entire file.
Next, the compiler makes several passes through the program source code to translate the code first to the assembly language of a target machine and then into machine code. The result is an object module consisting of machine code and tables of unresolved external references.
An object module cannot be loaded into memory or executed until it is linked to libraries and other modules to resolve external references. Hence, the final stage of compilation links a collection of object modules together to form an executable module with all the external references resolved. Only those parts in a library that corresponds to unresolved references are incorporated in the executable module. References present in shared libraries are loaded at run time using dynamic loading. To that end the compiler scans the shared libraries for references but does not put them in the executable module. Loading libraries is accomplished by explicitly specifying pathnames for directories to be searched for the libraries.
In more specific terms, compilation can be one phase in a more comprehensive language code processing. Considering, for example, a hardware design system in which the language used is any commercially available or proprietary hardware description language (HDL). HDL is a language typically used for conceptual design of integrated circuits. Verilog is an example of an HDL for electronic design and gate level simulation by Cadence Design Systems (hereafter xe2x80x9cCadencexe2x80x9d). Verilog is a trademark of Cadence.
Much like any other program, HDL programs have statements written based on language syntax, in this case HDL syntax. The data obstructions include data structures such as an electronic hardware database or components library (collectively referred to as the xe2x80x9cdatabasexe2x80x9d) that can be created and modified by the HDL program statements or code. A benefit provided by the use of the database is the creation and enforcement of standards. For example, the database defines common interfaces, buses, and building blocks. The database may also define common hardware specification and logic functionality. Engineers can refer to common information such as the common building blocks and interfaces information and develop in synch hardware, firmware and software.
In a concept-to-implementation loop of an integrated circuit design, HDL is used for modeling electronic hardware components of the integrated circuit, singly or in combination. Simulation and optimization are phases in the design loop following the generation, compilation and linking of the HDL programs. The concept-to-implementation loop is iterative. Namely, the conceptual design, HDL program generation and compilation, simulation, analysis, and adjustment cycle is repeated throughout the design process using various parameters in each iterations (e.g., timing specifications).
In order to make the concept-to-implementation loop efficient, more efficient simulation, optimization, and re-creation and compilation the HDL programs are required. Increased efficiency is required, for example, since the HDL programs generation, compilation and linking (hereafter xe2x80x9ccode processingxe2x80x9d) draws from the ever growing library of hardware building blocks to become more complex and time consuming.
For virtual implementation of circuits at any level including integrated circuits, the design process described above is interactive. Ideally, an interactive design process allows a user to virtually create, test and evaluate integrated circuits in real time. However, the complexity and time consumption of HDL programs code processing increases in a direct relationship with the increased complexity and size of the HDL programs and hardware libraries. For real large databases the interactive design cycle takes too long, i.e., it takes too long to add or retrieve information from the data base and process the HDL program code using this information. Hence, whether it is a commercially available HDL, such as Verilog, or a proprietary program language, the HDL program code processing efficiency need to be improved in order to improve the design cycle. The efficiency of code processing is of particular importance in an interactive design cycle.
Moreover, as a general observation, the efficiency of code processing is important for any given type of programming language. Accordingly, what is needed is a more efficient program code processing. The present invention addresses this and related problems.
The present invention relates to multithreaded program code processing. A preferred embodiment of the present invention provides multithreaded layered-code processing for improved efficiency of program code processing. Conceptually, the present invention breaks the task of program code processing into smaller tasks, i.e., threads, which can be executed concurrently. Concurrent processing of layers of code, through multithreading, is far more efficient then serial processing the layers of code. Preferably, the multithreading is implemented in a multiprocessor environment for concurrent execution of the multiple threads.
In accordance with the purpose of the invention, as embodied and broadly described herein, one aspect of the invention is a method including steps for the multithreaded processing of layered code. Another aspect of the invention is a computer readable medium. The computer readable medium embodies computer program code configured to cause a computer system to perform steps for the multithreaded processing of layered code.
In accordance with the preferred embodiment of the present invention, the steps include passing through the layered code to discover each layer of the layered code. The steps also include acquiring a lock when a layer is discovered, determining whether to spawn a thread to process the discovered layer, and, if it is so determined, spawning a thread to process the discovered layer. The steps further include releasing the lock once the new thread is either spawned or aborted, and, if spawned, proceeding with execution of the thread concurrently with other threads.
In further accordance with the purpose of the invention, as embodied and broadly described herein, an additional aspect of the invention is a multithreaded layered-code processor. Yet another aspect of the invention is a multithreaded layered-code processing system. The system includes a multiprocessor environment for concurrent execution of multiple threads, and a memory including a code processor.
The multithreaded layered-code processor and the code processor of the system (hereafter collectively referred to as xe2x80x9cthe code processorxe2x80x9d) similarly include means for passing through the layered code to discover each layer of the layered code, means for acquiring a lock when a layer is discovered and means for determining whether to spawn a thread to process the discovered layer. The code processor further includes means for spawning a thread, if it is so determined, for processing the discovered layer, means for releasing the lock, and means for proceeding with execution of the thread concurrently with other threads.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.